package com.leecode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: huangzhigao
 * @Date: 2022/4/7 16:50
 * 最小覆盖子串
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
 */
public class leecode76_minCoverLen {
    public static String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        char[] tChars = t.toCharArray();
        int count = 0;
        for (char c : tChars) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;

        int start = 0;
        int length = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c) == need.get(c)) {
                    count++;
                }
            }


            while (count == need.size()) {
                if (right - left < length) {
                    start = left;
                    length = right - left;
                }
                char d = s.charAt(left);
                //移除d
                left++;
                if (need.containsKey(d)) {
                    if (need.get(d) == window.get(d)) {
                        count--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }


        return length == Integer.MAX_VALUE ? "" : s.substring(start, length);
    }




    public String minWindow1(String s, String t) {
        int[] map = new int[256];
        char[] str = s.toCharArray();
        char[] target = t.toCharArray();
        for (char cha : target) {
            map[cha]++;
        }

        int L = 0;
        int R = 0;
        int all = target.length;
        int minLength = -1;

        int ansl = -1;
        int ansr = -1;

        while (R != str.length) {
            map[str[R]]--;
            if (map[str[R]] >= 0) {
                //有效匹配，因为map大于>0的元素，必然是t中出现的字符
                all--;
            }

            if (all == 0) {
                //收集答案
                while (map[str[L]] < 0) {
                    //不断缩小左侧不会造成匹配不上的字符，寻找出以r结果，能匹配上的最小字符
                    map[str[L++]]++;
                }
                if (minLength == -1 || minLength > R - L + 1) {
                    minLength = R - L + 1;
                    ansl = L;
                    ansr = R;
                }
                //此时让L继续往下划，使之开始又不匹配
                all++;
                map[str[L++]]++;
            }
            R++;
        }


        return minLength == -1 ? "" : s.substring(ansl, ansr + 1);
    }
}
